<?php
/**
 * Created by PhpStorm.
 * User: allen
 * Date: 2019/2/19
 * Time: 8:44 PM
 */

// 快速排序采用分治法实现排序，具体步骤：
// 1、从数列中挑出一个数作为基准元素。通常选择第一个或最后一个元素。
// 2、扫描数列，以基准元素为比较对象，把数列分成两个区。规则是：小的移动到基准元素前面，大的移到后面，相等的前后都可以。分区完成之后，基准元素就处于数列的中间位置。
// 3、然后再用同样的方法，递归地排序划分的两部分。
function quickSort($arr)
{
    $len = count($arr);

    // 先设定结束条件，判断是否需要继续进行
    if($len <= 1) {
        return $arr;
    }

    // 选择第一个元素作为基准元素
    $pivot = $arr[0];

    // 初始化左数组
    $left = $right = array();

    // 初始化大于基准元素的右数组
    $right = array();

    // 遍历除基准元素外的所有元素，按照大小关系放入左右数组内
    for ($i = 1; $i < $len ; $i++) {
        if ($arr[$i] < $pivot) {
            $left[] = $arr[$i];
        } else {
            $right[] = $arr[$i];
        }
    }

    // 再分别对左右数组进行相同的排序
    $left = quickSort($left);
    $right = quickSort($right);

    // 合并基准元素和左右数组
    return array_merge($left, array($pivot), $right);
}

$arr = [0,3,-1,10,5,20];
$arr = quickSort($arr);
print_r($arr);